5089. Словарь

Пётр решил составить толковый словарь орочьей речи. Он последовательно подходил к n оркам; каждый произносил ему одно слово на орочьем языке, и Пётр записывал это слово. Определений к словам он решил не добавлять – всё равно каждый орк знает их значение. Теперь вся работа, что остаётся выполнить вам (самому Петру это уже наскучило), – отсортировать полученный список слов в лексикографическом порядке.

Вход. В первой строке задано количество слов n (1 ≤ n ≤ 100).

В следующих n строках приведены слова орочьего языка, состоящие только из заглавных букв.

Длина каждого слова не превосходит 100 символов.

Выход. Выведите словарь Петра – n орочьих слов, отсортированных в лексикографическом порядке.

Пример входа	Пример выхода
3 AB A AA	A AA AB

РЕШЕНИЕ

структуры данных – set

Анализ алгоритма

Занесём все слова в множество строк, после чего выведем их в лексикографическом порядке.

Реализация алгоритма

Объявим множество строк s.

set<string> s;

Читаем количество слов n.

cin >> n;

Читаем слова и добавляем их во множество s.

for (i = 0; i < n; i++)

{

cin >> str;

s.insert(str);

}

Выводим слова в лексикографическом порядке.

for (string str : s)

cout << str << endl;

Реализация алгоритма – swap sort

#include <stdio.h>

#include <string.h>

#include <malloc.h>

char s[100][101];

char str[101];

int i, j, n, len;

int main(void)

{

scanf("%d\n", &n);

for (i = 0; i < n; i++)

{

gets_s(str);

strcpy(s[i], str);

}

for (i = 0; i < n; i++)

for (j = i + 1; j < n; j++)

if (strcmp(s[i], s[j]) > 0)

{

strcpy(str, s[i]);

strcpy(s[i], s[j]);

strcpy(s[j], str);

}

for (i = 0; i < n; i++)

puts(s[i]);

return 0;

}

Реализация алгоритма – swap sort, string

#include <iostream>

#include <string>

#include <vector>

using namespace std;

vector<string> s;

string str;

int i, j, n, len;

int main(void)

{

cin >> n;

for (i = 0; i < n; i++)

{

cin >> str;

s.push_back(str);

}

for (i = 0; i < n; i++)

for (j = i + 1; j < n; j++)

if (s[i] > s[j])

{

str = s[i];

s[i] = s[j];

s[j] = str;

}

for (i = 0; i < n; i++)

cout << s[i] << endl;

return 0;

}

Java реализация

import java.util.*;

public class Main

{

public static void main(String []args)

{

Scanner con = new Scanner(System.in);

TreeSet<String> s = new TreeSet<String>();

int n = con.nextInt();

for(int i = 0; i < n; i++)

s.add(con.next());

for(String st : s)

System.out.println(st);

con.close();

}

}